package day21;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 序列化是指将一个数据结构转化为位序列的过程，因此可以将其存储在文件中或内存缓冲区中，以便稍后在相同或不同的计算机环境中恢复结构。
 *
 * 设计一个序列化和反序列化 N 叉树的算法。一个 N 叉树是指每个节点都有不超过 N 个孩子节点的有根树。序列化 / 反序列化算法的算法实现没有限制。你只需要保证 N 叉树可以被序列化为一个字符串并且该字符串可以被反序列化成原树结构即可。
 *
 * 例如，你需要序列化下面的 3-叉 树。
 *
 *
 *
 *
 *
 *
 *
 * 为 [1 [3[5 6] 2 4]]。你不需要以这种形式完成，你可以自己创造和实现不同的方法。
 *
 * 或者，您可以遵循 LeetCode 的层序遍历序列化格式，其中每组孩子节点由空值分隔。
 *
 *
 *
 * 例如，上面的树可以序列化为 [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 *
 * 你不一定要遵循以上建议的格式，有很多不同的格式，所以请发挥创造力，想出不同的方法来完成本题。
 *
 *
 *
 * 示例 1:
 *
 * 输入: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 * 输出: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 * 示例 2:
 *
 * 输入: root = [1,null,3,2,4,null,5,6]
 * 输出: [1,null,3,2,4,null,5,6]
 * 示例 3:
 *
 * 输入: root = []
 * 输出: []
 *
 */
public class Codec {
    public String serialize(Node root) {
        if(root==null){
            return "";
        }
        StringBuilder str = new StringBuilder();
        str.append(root.val);
        List<Node> children = root.children;
        if(!children.isEmpty()){
            str.append(" ");
            str.append('(');
            for (Node child : children) {
                str.append(serialize(child));
            }
            str.append(')');
            str.append(" ");
        }
        return str.toString();
    }

    public Node deserialize(String data) {
        if(data.isEmpty()){
            return null;
        }
        String[] s = data.split(" ");
        Node root = new Node(Integer.parseInt(s[0]),new ArrayList<>());
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        for (int i = 1; i < s.length; i++) {
            if("(".equals(s[i])){
                continue;
            }else if(")".equals(s[i])){
                stack.pop();
            }else {
                Node node = new Node(Integer.parseInt(s[i]),new ArrayList<>());
                if(!"(".equals(s[i-1])){
                    stack.pop();
                }
                stack.peek().children.add(node);
                stack.push(node);
            }
        }
        return root;
    }
}
